#include<bits/stdc++.h>
using namespace std;

string delSpace(string x)
{
	int k = 0, len = x.size();
	for(int i = 0;i < len;i++)
	{
		if(x[i] != ' ')
			break;
		else
			k++;
	}
	string y(x, k, len-k);
	len = len-k;
//	for(int i = 0;i < len;i++)
//		y[i] = x[i+k];
	
	reverse(y.begin(), y.end());
	k = 0;
//	len = y.size();
	for(int i = 0;i < len;i++)
	{
		if(y[i] != ' ')
			break;
		else
			k++;
	}
	string z(y, k, len-k);
	len = len-k;
//	for(int i = 0;i < len;i++)
//		z[i] = y[i+k];
	reverse(z.begin(), z.end());
	
	return z;
}

char change(char ch)
{
	if('a' <= ch && ch <= 'z')
		return ch-('a'-'A');
	else
		return ch;
}

bool cmp(string x, string y)
{
	int len = min(x.size(), y.size());
	int i;
	for(i = 0;i <= len;i++)
	{
		if(change(x[i]) != change(y[i]))
			return change(x[i]) < change(y[i]);
	}
//	if(change(x[i]) != change(y[i]))
//			return change(x[i]) < change(y[i]);
}

int main()
{
	string method, s[100];
	int n;
	cin>>method>>n;
	cin.get();
	for(int i = 1;i <= n;i++)
	{
		getline(cin,s[i]);
		s[i] = delSpace(s[i]);
	}
		
		
//	getchar();
	if(method == "inc")
	{
		sort(s+1, s+n+1);
		for(int i = 1;i <= n;i++)
			cout<<s[i]<<endl;
	}
	else if(method == "dec")
	{
		sort(s+1, s+n+1);
		for(int i = n;i >= 1;i--)
			cout<<s[i]<<endl;
	}
	else if(method == "ncinc")
	{
		sort(s+1, s+n+1, cmp);
		for(int i = n;i >= 1;i--)
			cout<<s[i]<<endl;
	}
	else if(method == "ncdec")
	{
		sort(s+1, s+n+1, cmp);
		for(int i = n;i >= 1;i--)
			cout<<s[i]<<endl;
	}
    return 0;
}

